#include<iostream>
#include<vector>
#include<initializer_list>
#include<assert.h>
#include"reverse_iterator.hpp"
using namespace std;

namespace Mango
{
//节点类
template<class T>
struct ListNode
{
	T _val;
	ListNode<T>* _next;
	ListNode<T>* _prev;
	
	ListNode(const T& val = T())
		:_val(val),_next(nullptr),_prev(nullptr)
	{}	
};

//迭代器类
template<class T,class Ref,class Ptr>
class _list_iterator
{
public:
	typedef ListNode<T> ListNode;	//节点类型
	typedef _list_iterator<T,Ref,Ptr> self;//迭代器类型
	_list_iterator(ListNode* node )
	{
		_node = node;
	}
	//运算符重载函数
	self& operator++() //前置
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node -> _prev;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	bool operator==(const self& s) const
	{
		return this->_node == s._node;
	}
	bool operator!=(const self& s) const
	{
		return this->_node != s._node;
	}
	Ref operator*()
	{
		return _node->_val;
	}
	Ptr operator->()
	{
		return	&_node->_val;
	}

	ListNode* _node;
};


template<class T>
class list
{
public:
	//构造函数，拷贝构造函数,赋值重载函数,析构函数
	typedef ListNode<T> ListNode;
	list()
	{
		_head = new ListNode;
		_head->_prev = _head;
		_head->_next = _head;	
	}
	list(size_t n ,const T& val = T())
	{
		_head = new ListNode;
		_head->_prev = _head;
		_head->_next = _head;
		for(size_t i = 0;i<n;i++)
		{
			push_back(val);
		}
	}
	
	list(int n ,const T& val = T()) //函数重载版本
	{
		_head = new ListNode;
		_head->_prev = _head;
		_head->_next = _head;
		for(int i = 0;i<n;i++)
		{
			push_back(val);
		}
	}
	template<class InputIterator>
	list(InputIterator first,InputIterator last) //迭代器区间初始化
	{
		_head = new ListNode;
		_head->_prev = _head;
		_head->_next = _head;
		while(first != last)
		{
			push_back(first);
			++first;
		}
	}
	list(initializer_list<T> ilt)
	{
		_head = new ListNode;
		_head->_prev = _head;
		_head->_next = _head;
		for(auto& e:ilt)
		{
			push_back(e);	
		}		
	}
	
	list(const list<T>& lt)
	{
		_head = new ListNode;
		_head->_prev = _head;
		_head->_next = _head;
		
		for(auto& e:lt)
		{
			push_back(e);
		}
	}
	
	//现代写法
//	list(const list<T>& lt)
//	{
//		_head = new ListNode;
//		_head->_prev = _head;
//		_head->_next = _head;
//		list<T> tmp(lt.begin(),lt.end());
//		swap(_head,lt._head);
//	}
	
	//list<T>& operator=(const list<T>& lt)
	//{
	//	if(this != &lt)
	//	{
	//		clear();
	//		for(auto& e: lt)
	//		{
	//			push_back(e);	
	//		}	
	//	}
	//	return *this;
	//}
	//
	//现代写法
	list<T>& operator=(list<T> lt)
	{
		if(this!=&lt)
		{
			::swap(lt._head,_head);
		}
		return *this;
	}
	
	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	//迭代器
	typedef _list_iterator<T,T&,T*> iterator;
	typedef _list_iterator<T,const T&,const T*> const_iterator;
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}
	const_iterator end() const
	{
		return const_iterator(_head);
	}
	
	void PrintList()
	{
		auto it = begin();
		while(it!= end())
		{
			cout << *it<<" ";
			it++;
		}
		cout << endl;
	}
	
	//增删查改
	T& front() 
	{
		return *begin();
	}
	const T& front()  const
	{
		return *begin();
	}
	T& back() 
	{
		return _head->_prev->_val;
	}
	const T& back() const
	{
		return _head->_prev->_val;
	}
	iterator insert(iterator pos,const T& x) //在pos迭代器前插入
	{
		assert(pos._node);
		ListNode* cur = pos._node;
		ListNode* newnode = new ListNode(x);
		ListNode* prev = cur->_prev;
		//prev newnode cur
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = cur;
		cur->_prev = newnode;
		
		return iterator(newnode);//返回插入位置的迭代器
	}
	iterator erase(iterator pos) //删除pos位置的迭代器
	{
		assert(pos._node);
		ListNode* cur = pos._node;
		ListNode* next = cur->_next;
		ListNode* prev = cur->_prev;
		//prev next
		prev->_next = next;
		next->_prev = prev;
		delete cur;
		return iterator(next);
	}
	void push_back(const T& x)
	{
		ListNode* back = _head->_prev;
		ListNode* newnode = new ListNode(x);
		//_head back newnode
		_head->_prev = newnode;
		newnode->_next = _head;
		back->_next = newnode;
		newnode->_prev = back;
		
		//insert(end(),x);
	}
	void pop_back()
	{
		if(_head->_next == _head->_prev) //只有哨兵位节点,不能删除
		{
			return ;
		}
		ListNode* back = _head->_prev;
		ListNode* prev = back->_prev;
		//_head prev
		_head->_next = prev;
		prev->_next = _head;
		delete back;
		
		//erase(--end())
	}
	void push_front(const T& x)
	{
		ListNode* newnode = new ListNode(x);
		ListNode* cur = _head->_next;
		//_head newnode cur
		_head->_next = newnode;
		newnode->_prev = _head;
		newnode->_next = cur;
		cur->_prev = newnode;
		//insert(begin(),x);
	}
	void pop_front(const T& x)
	{
		if(_head->_next == _head->_prev) //只有哨兵位节点,不能删除
		{
			return ;
		}
		ListNode* del = _head->_next;
		ListNode* next = del->_next;
		//_head next
		_head->_next = next;
		next -> _prev = _head;
		
		//erase(begin());
	}
	size_t size()
	{
		size_t len = 0;
		ListNode* cur = _head;
		while(cur->next != _head)
		{
			len++;
			cur = cur->next;
		}
		return len;
	}
	void clear()
	{
		ListNode* cur = _head->_next;
		while(cur->_next != _head)
		{
			ListNode* next = cur->_next;//保存下一个节点
			delete cur;//释放当前节点
			cur = next;
		}
		//最后记得让哨兵位重新指向自己
		_head->_prev = _head;
		_head->_next = _head;
	}
	bool empty() const
	{
		return begin() == end(); //return _head->_prev == _head->_next;
	}
	void resize(size_t n ,const T& val = T())
	{
		int len = 0;
		auto it = begin();
		while(len < n && it != end())
		{
			len++;
			it++;
		}
		if(len == n) //后面的数据都要删掉
		{
			while(it!=end())
			{
				it = erase(it);
			}
		}
		else //扩容
		{
			while(len < n)
			{
				push_back(val);
				len++;
			}
		}
	}
	//反向迭代器
	typedef Mango::reverse_iterator<iterator,T&,T*> reverse_iterator;
	typedef Mango::reverse_iterator<const_iterator,const T&,const T*> const_reverse_iterator;
	
	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}
	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}
	
	const_reverse_iterator rbegin() const
	{
		return const_reverse_iterator(end());		
	}
	const_reverse_iterator rend()  const
	{
		return const_reverse_iterator(begin());	
	}
private:
	ListNode* _head; //指向哨兵位节点
}; 
}